package com.example.Arithmetic.Arithmetic;

import java.util.Scanner;


public class 二分查找 {
    public static int[] target = {1, 4, 6, 8, 11, 15, 17, 20, 20, 30};

    public static void main(String[] args) {
        System.out.println("请输入要查找的数字");
        Scanner scanner = new Scanner(System.in);
        int s = scanner.nextInt();
        int 查找 = 二分查找.查找(target, s);       //基础版二分查找，i和j可以在同一个索引
        System.out.println(查找);

        查找 = 二分查找.查找改进(target, s);       //改进版二分查找，j做边界值
        System.out.println(查找);

        查找 = 二分查找.查找改进for(target, s);    //for循环版二分查找
        System.out.println(查找);

        查找 = 二分查找.查找再改进(target, s);     //左右平衡查找，解决右查找时间复杂度比左查找高2倍情况
        System.out.println(查找);

        查找 = 二分查找.查找重复值(target, s);     //查找出重复值中最靠左的
        System.out.println(查找);

        查找 = 二分查找.递归查找(target, s, 0, target.length);     //查找出重复值中最靠左的
        System.out.println("递归:" + 查找);
    }


    public static int 查找(int[] target, int w) {
        int i = 0;
        int j = target.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (w < target[m]) {
                j = m - 1;
            } else if (target[m] < w) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    public static int 查找改进(int[] target, int w) {
        int i = 0;
        int j = target.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (w < target[m]) {
                j = m;
            } else if (target[m] < w) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    public static int 查找改进for(int[] target, int w) {
        int i = 0;
        int j = target.length;
        for (i = 0; i < j; ) {
            int m = (i + j) >>> 1;
            if (target[m] < w) {
                i = m + 1;
            } else if (w < target[m]) {
                j = m;
            } else {
                return m;
            }
        }
        return -1;
    }


    public static int 查找再改进(int[] target, int w) {
        int i = 0, j = target.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (w < target[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (target[i] == w) {
            return i;
        }
        return -1;
    }


    public static int 查找重复值(int[] target, int w) {
        int i = 0;
        int j = target.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (w < target[m]) {
                j = m - 1;
            } else if (target[m] < w) {
                i = m + 1;
            } else {
                candidate = m;
            }
        }
        return candidate;
    }

    public static int 递归查找(int[] target, int w, int i, int j) {
        if (target[target.length - 1] < w) {
            return -1;
        }
        if (i > j) {
            return -1;
        }
        int m = (i + j) >>> 1;
        if (w < target[m]) {
            return 递归查找(target, w, i, m - 1);
        } else if (target[m] < w) {
            return 递归查找(target, w, m + 1, j);
        } else {
            return m;
        }
    }
}
